package 打牢基础30天.day02.my;

/**
 * @Author yaya
 * @Create 2024/6/13 10:06
 * Description:荷兰国旗问题
 */
public class Code05_NetherlandsFlag {
    /**
     * 给定一个数，使其前部分为小于target的数，中间为等于target的数，后部分为大于target的数
     * @param arr
     * @param target
     * @return 中间值的边界
     */
    public static int[] netherlandsFlag(int[] arr, int target, int left, int right){
        // 小值、大指边界
        int less = left - 1;
        int more = right + 1;

        // 左指针碰到大值边界就说明已经扫完了
        // 1、如果碰到小值，塞入小值边界中，left++，++less当前 left指针 与小 值边界+1位置 交换
        // 2、如果碰到大值，塞入大值边界中，more--, left指针与大值边界more交换，交换后因为left未扫描，所以left不增加
        // 3、碰到等值就left++
        while (left < more){
            if (arr[left] < target){
                swap(arr,++less, left++);
            }else if (arr[left] > target){
                swap(arr, --more,left);
            }else {
                left++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
